import java.util.*;
//链表的回文结构

 class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        ListNode slow = A;
        ListNode fast = A;
        //slow 为中间节点
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast= fast.next.next;
        }

        //从中间往后开始反转链表
        //记得要把中间结点的next置为null，否则会形成环形链表，虽然本质上是反转链表，但是还是要跟反转整个链表一样要把头的next给置null
        ListNode cur=slow;
        ListNode pre=null;
        while(cur!=null){
            ListNode curN=cur.next;
            cur.next=pre;
            pre=cur;
            cur=curN;
        }

        //判断是否为回文
        ListNode headA=A;
        ListNode headB=pre;
        while(headB!=null){
            if(headA.val!=headB.val){
                return false;
            }
            headA=headA.next;
            headB=headB.next;
        }
        return true;
    }
}